// Floyd
// https://www.luogu.com.cn/problem/P1119

const int maxn = 5 + 1e5;
int n;
int adj[maxn][maxn];

void Update(int k) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (adj[i][j] > adj[i][k] + adj[k][j])
                adj[i][j] = adj[i][k] + adj[k][j];
}
void Floyd() {
    for (int k = 1; k <= n; ++k) Update(k);
}
